In recent years, autonomous distributed networks are used, which are ad-hoc networks or the like and formed by communication between communication devices and do not use a network infrastructure including a base station, an access point, and the like.
In an autonomous distributed network, many communication devices are connected to each other without an access point by using a technique used for wireless connections of, for example, computers, personal digital assistants (PDAs), mobile phones, and the like. The many communication devices each transmit and receive a packet by multi-hop communication. The multi-hop communication is a technique that enables each of communication devices that exist in different communication areas to communicate with the other communication device through another communication device that exists in the communication area in which the interested communication device exists. The communication devices are referred to as nodes that exist in the network.
Traditionally, a technique for causing the nodes to form communication paths in the network is known. Each of the nodes uses this technique to autonomously form communication paths extending from the interested node to a final destination of a data packet. Each of the nodes treats, as a priority path, a communication path that is among paths extending from the interested node to the final destination and of which the quality is highest. The smaller a path cost that depends on the number of hops and the like in multi-hop communication, the higher the quality of the path.
A topology is frequently changed in the autonomous distributed network, unlike a traditional fixed network. Thus, a priority path formed upon, the formation of the paths may not be used for actual transmission of a data packet. In consideration of such situations, each of the nodes holds an alternative path that is not a priority path and is among a plurality of communication paths. For example, if a communication failure occurs in a priority path, an interested node transmits a data packet using an alternative path.
As a method for determining an alternative path, a method for selecting, as the alternative path, a communication path in which the number of hops is small is known, for example. In addition, a method for selecting an alternative path based on a spatial correlation between the alternative path and a priority path is also known.
In addition, there is a method in which a path request message that is used for routing includes a relay node list field in order to form paths and is discarded by each of nodes if addresses of the nodes exist in the relay node list field. Specifically, the method inhibits the path request message from being looped and enables the nodes to form a plurality of paths that are not looped.
In addition, for formation of a path related to a wired ad-hoc network, there is a method for learning the occurrence of a loop by a certain node device when a first frame transmitted by the certain node device is looped in the network and received as a second frame by the certain node device. The node device uses a loop detection table to learn a port that causes the occurrence of the loop. Then, the node device does not transmit a frame to the port that causes the occurrence of the loop.
Those methods are disclosed in, for example, Japanese Laid-open Patent Publications Nos. 2004-336767, 2005-252452, 2005-64721, and 2006-20221 and International Publication No. WO2010/131288.